package com.example.queue;

import java.util.Deque;
import java.util.LinkedList;

/**
 * ping(int t)在时间 t 添加一个新请求，其中 t 表示以毫秒为单位的某个时间，并返回过去 3000 毫秒内发生的所有请求数（包括新请求）
 * 确切地说，返回在 [t-3000, t] 内发生的请求数。
 * 每次对 ping 的调用都使用比之前更大的 t 值。
 * 至多调用 ping 方法 10000 次
 * <p>
 * 示例
 * recentCounter.ping(1);     // requests = [1]，范围是 [-2999,1]，返回 1
 * recentCounter.ping(100);   // requests = [1, 100]，范围是 [-2900,100]，返回 2
 * recentCounter.ping(3001);  // requests = [1, 100, 3001]，范围是 [1,3001]，返回 3
 * recentCounter.ping(3002);  // requests = [1, 100, 3001, 3002]，范围是 [2,3002]，返回 3
 */
public class Leetcode933_RecentCounter {
    public static void main(String[] args) {
        RecentCounter2 recentCounter = new RecentCounter2();
        System.out.println(recentCounter.ping(1178));
        System.out.println(recentCounter.ping(1483));
        System.out.println(recentCounter.ping(1563));
        System.out.println(recentCounter.ping(4054));
        System.out.println(recentCounter.ping(4152));

    }

    /**
     * 解法一:暴力解法
     * 第一种方式:
     * 1.创建数组，存放所有的请求(整型数组，存放10000个元素)
     * 2.把当前请求存入数组
     * 主要是ping(t) t是递增的，所以直接可以遍历数组不为0的地方将数据存入即可
     * 3.统计距离此次请求前3000毫秒之间的请求次数
     * 从最后一次存放位置倒序遍历
     * <p>
     * 第二种方式:(内存占用过多不行)
     * 1.创建数组，存放所有的请求(整型数组，存放10^9个元素)
     * 当请求来到的时候将对应下标的数组数据置为1
     * 对当前数组下标t-3000 ~ t 求和 返回
     * <p>
     * 注意点:
     * t-3000可能为负
     */
    private static class RecentCounter {
        private int[] allRequest = new int[10000];

        public RecentCounter() {
        }

        public int ping(int t) {
            // 用于记录当前请求的索引
            int end = 0;

            for (int i = 0; i < allRequest.length; i++) {
                // 数组数据为0，说明该位置没被存数据,就将本次请求放入其中
                if (allRequest[i] == 0) {
                    allRequest[i] = t;
                    end = i;
                    break;
                }
            }

            int count = 0;
            // 从end向前遍历3000个数据，一旦索引小于0则退出，否则count++
            for (int i = 0; i <= 3000; i++) {
                if (end - i < 0) {
                    break;
                }
                count++;
            }

            return count;
        }

        // 不可行方案
        public int ping2(int t) {
            allRequest[t - 1] = 1;
            int result = 0;
            for (int i = 0; i <= 3000; i++) {
                // t-3000 为负就直接退出循环
                if (t - i - 1 < 0) {
                    break;
                }
                result += allRequest[t - i - 1];
            }
            return result;
        }
    }


    /**
     * 解法二:双指针法(优化)
     * <p>
     * 1.创建数组存放请求：int[3002]
     * 2.额外定义开始指针
     * start=0，end=0，记录起止索引
     * 3.存放请求后，更新起止索引
     * end++; 从上次的开始索引（start）向后查找
     * 直到新的合法的起始位置
     * 4.通过end与start差值计算请求次数
     * <p>
     * 注意点:
     * start\end 有可能会超过request.length
     * <p>
     * 该方式其实类似于用循环队列的方式
     */
    private static class RecentCounter2 {
        private int[] requests = new int[3002];
        private int start = 0, end = 0;


        public int ping(int t) {
            requests[end++] = t;
            // end指针越界后，直接归0(其实就是将前3000以上的请求数据覆盖掉)
            // 因为只是要计算前3000ms到当前t的请求次数，因此不可能超过3000
            end = end == requests.length ? 0 : end;

            // 过滤掉所有不符合要求的数
            // 当下标start对应的值比t-3000还小,start指针需要后移
            while (t - requests[start] > 3000) {
                start++;
                // 当start指针越界后，也可以直接归0
                start = start == requests.length ? 0 : start;
            }

            // 通过end与start差值计算请求次数
            // 请求次数超过数组容量，发生了溢出
            if (start > end) {
                return requests.length - (start - end);
            }
            // 此时，end为最新一次请求 + 1 的索引，start是3000毫秒前的第一次合法请求索引
            return end - start;
        }
    }


    /**
     * 解法三:队列
     * <p>
     * 实现:每次请求来的数据入队时就去检查队头是否有比当前要入队的这个时间点的请求要早3000ms 的数据
     * 如果有则循环将其出队
     */
    private class RecentCounter3 {
        private Deque<Integer> queue = new LinkedList<>();

        public RecentCounter3() {
        }

        public int ping(int t) {
            queue.add(t);
            while (queue.peek() < t - 3000) {
                queue.poll();
            }
            return queue.size();
        }
    }
}
